package baseclass.b_stackQueue;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 获取队列的最小值
 * 4 3 3 5 2 5
 * 使用一个非单调递减双端队列minQ。
 * 入队4 minQ入队4
 * 入队3 4>3  minQ出队4，放入3
 * 入队3 3= 3 minQ放入3
 *
 * 此时4出队，minQ队头是3，不更新
 * 此时3出队，minQ队头是3，弹出3
 *
 * 入队5 3<5  minQ入队5，此时为3，5
 * 入队2 3，5  >2   minQ出队，为空后，入队2
 * 入队5  2<5   minQ入队5，此时为2,5
 *
 * @date 2020/4/24 18:16
 */
public class Code04_GetQueueMin {
    Queue<Integer> queue = new LinkedList<>();
    Deque<Integer> minQ = new LinkedList<>();
    public void offer(int e){
        queue.offer(e);
        while (!minQ.isEmpty() && e < minQ.peekLast()){
            minQ.pollLast();
        }
        minQ.offer(e);
    }
    public int poll(){
        int e = queue.poll();
        if(e == minQ.peek())
            minQ.poll();
        return e;
    }
    public int getMin(){
        return minQ.peek();
    }
    public boolean isEmpty(){
        return queue.isEmpty();
    }

    public static void main(String[] args) {
        Code04_GetQueueMin queue = new Code04_GetQueueMin();
        queue.offer(1);
        System.out.println(queue.getMin());
        queue.offer(4);
        System.out.println(queue.getMin());
        queue.offer(3);
        System.out.println(queue.getMin());
        queue.offer(3);
        System.out.println(queue.getMin());
        queue.offer(5);
        System.out.println(queue.getMin());
        queue.offer(2);
        System.out.println(queue.getMin());
        queue.offer(5);
        System.out.println(queue.getMin());
        System.out.println("==============");
        while (!queue.isEmpty()){
            System.out.println(queue.getMin());
            queue.poll();
        }

    }
}
